package com.suanfa.dp;

/**
 * 矩阵路线计数
 */
public class MatrixRouteCount {


    public static int uniquePaths(int m, int n){
        int[][]dp = new int[m][n];
        //边界条件
        for(int i =0; i< m; i++){
            dp[i][0] = 1;
        }
        for(int i =0; i< n; i++){
            dp[0][i] = 1;
        }

        //状态转移方程
        for(int i =1; i< m; i++){
            for(int j = 1; j< n; j++){
                dp[i][j] = dp[i-1][j]+ dp[i][j-1];
            }
        }

        return dp[m-1][n-1];



    }
}
